/*-----------------------------------------------------------------------------------------------
PROJECT 1. SYNTAX ANALYSIS
==========================

IMPORTANT: IT WILL TAKE AROUND    20 HOURS           TO FINISH THIS PROJECT


The goal of this project is to write a recursive descent parser for a 
grammar and have the parser output a modified version of the input
program. The grammar is the following

program           -> decl body
decl              -> type_decl_section var_decl_section
type_decl_section -> TYPE type_decl_list 
type_decl_section ->                                          // epsilon
type_decl_list    -> type_decl type_decl_list
type_decl_list    -> type_decl
type_decl         -> id_list COLON type_name SEMICOLON
type_name         -> REAL
type_name         -> INT
type_name         -> BOOLEAN
type_name         -> STRING
type_name         -> ID
var_decl_section  -> VAR var_decl_list
var_decl_section  ->                                           // epsilon
var_decl_list     -> var_decl var_decl_list
var_decl_list     -> var_decl
var_decl          -> id_list COLON type_name SEMICOLON
id_list           -> ID COMMA id_list
id_list           -> ID
body              -> LBRACE stmt_list RBRACE
stmt_list         -> stmt stmt_list
stmt_list         -> stmt
stmt              -> while_stmt
stmt              -> assign_stmt
while_stmt        -> WHILE condition body
assign_stmt       -> ID EQUAL expr SEMICOLON
expr              -> term PLUS expr
expr              -> term MINUS expr
expr              -> term
term              -> factor MULT term
term              -> factor DIV term
term              -> factor
factor            -> LPAREN expr RPAREN
factor            -> NUM
factor            -> REALNUM
factor            -> primary
condition         -> primary relop primary
primary           -> ID
primary           -> NUM
primary           -> REALNUM
relop             -> GREATER
relop             -> GTEQ
relop             -> LESS
relop             -> NOTEQUAL
relop             -> LTEQ


Note that the grammar has a number of new tokens. They are: TYPE, BOOLEAN, 
LBRACE (left curly bracket: '{' ) and RBRACE (right curley bracket: '}' ). 
I already modified getToken() to handle these tokens.


PROJECT 1 REQUIREMENTS
======================

You should write all the functions to parse the grammar. The output is identical
to the input except that all expressions are changed to prefix notation.

I have already written the functions to parse some of the grammar constructs,
especially declarations. Also, I build a parse tree for variable declarations.
You should write the remaining functions and build the parse tree for the whole
grammar.

I have included declarations for the nodes of the parse tree. Expressions are
handled differently as the goal is to build an Abstract Syntax Tree (AST).
An example will illustrate this point.

Consider the expressions a+b*c+d. The AST for this expression is

__ +__
/      \
a        +
/ \ 
*   d
/ \   
b   c  

The type declarations I give for expressions, terms and factor are made for an AST. 
Given an AST, it is easy to print it in prefix notation. Simply print it in pre-order
traversal (print node then children).

Note that boolean expressions are also expressions and should be printed in prefix
notation.

REALNUM values are stored in the fval field of the primaryNode structure, which is a
floating point field. When printed, these values might come out in a format different 
from the input format. To standarize the output, I require that you use the following 
in printing floating point values.

printf("%.4f", x);

where x is a floating point number. This will ensure that exactly 4 digits after the
decimal point are printed.

EXAMPLE

VAR  a : INT;
{
a = a+1;
}


The output is

VAR 
a : INT ; 
{ 
a = + a 1 ; 
}


Note that this time I have split the program file into .c and .h parts.

If you are unsure of something, you should ask questions. Do not wait until the day
before the project is due to ask questions.


WHAT TO SUBMIT
==============

You should submit one zip file containing your program file(s).  All your
program files should be names


CHECKLIST
- compile on general
- test on general
- submit zip file according to naming convention in syllabus
- make sure that the name of each individual project file also
follow the same naming convention as for the zip file (with .c
and .h extensions obviously)
- make sure you write your full name as a comment in very file
you submit


IMPORTANT: IT WILL TAKE AROUND 20 HOURS TO FINISH THIS PROJECT

----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "syntax.h"

#define TRUE 1
#define FALSE 0

//----------------------------- token types ------------------------------
#define KEYWORDS 14
#define RESERVED 38
#define VAR 1
#define BEGIN 2
#define END 3
#define ASSIGN 4 
#define IF 5
#define WHILE 6 
#define DO 7
#define THEN 8
#define PRINT 9
#define INT 10
#define REAL 11
#define STRING 12
#define BOOLEAN 13
#define TYPE 14
#define PLUS 15
#define MINUS 16
#define DIV 17
#define MULT 18
#define EQUAL 19
#define COLON 20 
#define COMMA 21
#define SEMICOLON 22
#define LBRAC 23
#define RBRAC 24
#define LPAREN 25
#define RPAREN 26
#define NOTEQUAL 27
#define GREATER 28
#define LESS 29
#define LTEQ 30
#define GTEQ 31
#define DOT 32
#define ID 33
#define NUM 34
#define REALNUM 35
#define ERROR 36
#define LBRACE 37
#define RBRACE 38
#define NOOP 39

//------------------- reserved words and token strings -----------------------
char *reserved[] = 
{	"",
"VAR", 
"BEGIN", 
"END", 
"ASSIGN", 
"IF", 
"WHILE", 
"DO", 
"THEN", 
"print", 
"INT",
"REAL",
"STRING",
"BOOLEAN",
"TYPE",
"+",
"-", 
"/", 
"*", 
"=", 
":", 
",", 
";", 
"[", 
"]", 
"(", 
")", 
"<>", 
">", 
"<",
"<=",
">=",
".",
"ID",
"NUM",
"REALNUM",		
"ERROR",
"{",
"}"
};

int printToken(int ttype)
{
	if (ttype <= RESERVED)
	{   printf("%s\n",reserved[ttype]);
	return 1;
	} else
		return 0; 
}
//---------------------------------------------------------

//---------------------------------------------------------
// Global Variables associated with the next input token
#define MAX_TOKEN_LENGTH 100

char token[MAX_TOKEN_LENGTH];      // token string
int  ttype;                        // token type
int  activeToken = FALSE;                  
int  tokenLength;


int line_no = 1;

//----------------------------------------------------------
int skipSpace()
{
	char c;

	c = getchar(); 
	line_no += (c == '\n');
	while (!feof(stdin) && isspace(c))
	{    c = getchar(); 
	line_no += (c == '\n');
	}

	// return character to input buffer if eof is not reached
	if (!feof(stdin)) 
		ungetc(c,stdin);
}

int isKeyword(char *s)
{
	int i;

	for (i = 1; i <= KEYWORDS; i++)
		if (strcmp(reserved[i],s) == 0)
			return i;
	return FALSE;
}

// ungetToken() simply sets a flag so that when getToken() is called
// the old ttype is returned and the old token is not overwritten 
// NOTE: BETWEEN ANY TWO SEPARATE CALLS TO ungetToken() THERE MUST BE
// AT LEAST ONE CALL TO getToken()
// CALLING TWO ungetToken() WILL NOT UNGET TWO TOKENS  
void ungetToken()
{
	activeToken = TRUE;
}


int scan_number()
{
	char c;

	c = getchar();
	if (isdigit(c))
	{	// First collect leading digits before dot
		// 0 is a nNUM by itself
		if (c == '0')	      
		{	token[tokenLength] = c;
		tokenLength++;
		token[tokenLength] = '\0';
		} else
		{	while (isdigit(c))
		{	token[tokenLength] = c;
		tokenLength++;;
		c = getchar();
		}
		ungetc(c,stdin);
		token[tokenLength] = '\0';
		}

		// Check if leading digits are integer part of a REALNUM
		c = getchar();
		if (c == '.')
		{	c = getchar();
		if (isdigit(c))
		{	token[tokenLength] = '.';
		tokenLength++;
		while (isdigit(c))
		{	token[tokenLength] = c;
		tokenLength++;
		c = getchar();
		}
		token[tokenLength] = '\0';
		if (!feof(stdin)) 
			ungetc(c,stdin);
		return REALNUM;
		} else
		{	ungetc(c, stdin);    // note that ungetc returns characters on a stack, so we first
		c = '.';             // return the second character and set c to '.' and return c again
		ungetc(c,stdin);				                                 
		return  NUM;         
		}
		} else
		{	ungetc(c, stdin);
		return NUM;
		}
	} else
		return ERROR;   
}


int scan_id_or_keyword()
{
	int ttype;
	char c;

	c = getchar();
	if (isalpha(c))
	{	while (isalnum(c))
	{	token[tokenLength] = c;
	tokenLength++;
	c = getchar();
	}
	if (!feof(stdin)) 
		ungetc(c,stdin); 

	token[tokenLength] = '\0';		                
	ttype = isKeyword(token); 
	if (ttype == 0) 
		ttype = ID;
	return ttype;
	} else
		return ERROR;
}                            


int getToken()
{	char c;

if (activeToken)
{ activeToken = FALSE;
return ttype;
}   // we do not need an else because the function returns in the body 
// of the if

skipSpace();   
tokenLength = 0;
c = getchar();
switch (c)
{   case '.': return DOT;
case '+': return PLUS;
case '-': return MINUS;
case '/': return DIV;
case '*': return MULT;
case '=': return EQUAL;
case ':': return COLON;
case ',': return COMMA;
case ';': return SEMICOLON;
case '[': return LBRAC;
case ']': return RBRAC;
case '(': return LPAREN;
case ')': return RPAREN;
case '{': return LBRACE;
case '}': return RBRACE;
case '<':
	c = getchar();
	if (c == '=')
		return LTEQ;
	else
		if (c == '>')
			return NOTEQUAL;
		else
		{
			ungetc(c,stdin);
			return LESS;
		}
case '>': 
	c = getchar();
	if (c == '=')
		return GTEQ;
	else
	{
		ungetc(c, stdin);
		return GREATER;
	}

default :
	if (isdigit(c))
	{	ungetc(c,stdin);
	return scan_number();
	}
	else
		if (isalpha(c))
		{	ungetc(c,stdin);
	return scan_id_or_keyword();
	}
		else
			if (c == EOF)
				return EOF;
			else
				return ERROR;
}
}



/*----------------------------------------------------------------------------
SYNTAX ANALYSIS SECTION
----------------------------------------------------------------------------*/
#define PRIMARY 0
#define EXPR 1

/*-------------------------------UTILITIES---------------------------*/
void syntax_error(char* NT, int line_no)
{
	printf("Syntax error while parsing %s line %d\n", NT, line_no);
}

/*--------------------------------------------------------------------
PRINTING PARSE TREE
---------------------------------------------------------------------*/
void print_parse_tree(struct programNode* program)
{	
	print_decl(program->decl); 
	print_body(program->body);
}



void print_body(struct bodyNode* body)
{
	printf("{\n");

	if(body->stmt_list != NULL)
	{
		print_stmt_list(body->stmt_list);

		printf("}\n");
	}


}

void print_decl(struct declNode* dec)
{
	if (dec->type_decl_section != NULL)
	{	
		print_type_decl_section(dec->type_decl_section);
	}
	if (dec->var_decl_section != NULL)
	{	
		print_var_decl_section(dec->var_decl_section);
	}
}


void print_var_decl_section(struct var_decl_sectionNode* varDeclSection)
{
	printf("VAR\n");
	if (varDeclSection->var_decl_list != NULL)
		print_var_decl_list(varDeclSection->var_decl_list);
}

void print_var_decl_list(struct var_decl_listNode* varDeclList)
{
	//if(varDeclList->var_decl != NULL)
	print_var_decl(varDeclList->var_decl);
	if (varDeclList->var_decl_list != NULL)
		print_var_decl_list(varDeclList->var_decl_list);	
}

void print_var_decl(struct var_declNode* varDecl)
{	
	print_id_list(varDecl->id_list);
	printf(": ");
	print_type_name(varDecl->type_name);
	printf(";\n");
}

void print_type_decl_section(struct type_decl_sectionNode* typeDeclSection)
{
	printf("TYPE\n");

	if(typeDeclSection->type_decl_list != NULL)
	{
		print_type_decl_list(typeDeclSection->type_decl_list);
	}
}

void print_type_decl_list(struct type_decl_listNode* typeDeclList)
{
	print_type_decl(typeDeclList->type_decl);

	if (typeDeclList->type_decl_list != NULL)
	{
		print_type_decl_list(typeDeclList->type_decl_list);
	}
}

void print_type_decl(struct type_declNode* typeDecl)
{	
	print_id_list(typeDecl->id_list);
	printf(": ");
	print_type_name(typeDecl->type_name);
	printf(";\n");
}

void print_type_name(struct type_nameNode* typeName)
{
	if (typeName->type != ID)
		printf("%s ", reserved[typeName->type]);
	else
		printf("%s ", typeName->id);
}

void print_id_list(struct id_listNode* idList)
{
	printf("%s ",idList->id);
	if (idList->id_list != NULL)
	{	printf(", ");
	print_id_list(idList->id_list);
	}
}

void print_stmt_list(struct stmt_listNode* stmt_list)
{
	if(stmt_list->stmt != NULL)
		print_stmt(stmt_list->stmt);

	if (stmt_list->stmt_list != NULL)
		print_stmt_list(stmt_list->stmt_list);
}

void print_assign_stmt(struct assign_stmtNode* assign_stmt)
{
	printf("%s = ", assign_stmt->id);
	if(assign_stmt->expr != NULL)
		print_expr_prefix(assign_stmt->expr);
	printf(";\n");
}

void print_while_stmt(struct while_stmtNode* while_stmt)
{
	printf("WHILE\n");

	print_condition(while_stmt->condition);
	if(while_stmt->body != NULL)
	print_body(while_stmt->body);
}
void print_stmt(struct stmtNode* stmt)
{
	if(stmt->stmtType == WHILE)
	{
		print_while_stmt(stmt->while_stmt);
	}
	else if(stmt->stmtType == ASSIGN)
	{
		print_assign_stmt(stmt->assign_stmt);
	}
}
//
//void print_expr_prefix(struct exprNode* expr)
//{
//	if(expr->tag == primary())
//	{
//		if(expr->primary->tag == ID)
//		{
//			printf("%s ", expr->primary->id);
//		}
//		else if(expr->primary->tag == NUM)
//		{
//			printf("%d ", expr->primary->ival);
//		}
//		else if(expr->primary->tag == REALNUM)
//		{
//			printf("%.4f ", expr->primary->fval);
//		}
//	}
//	else
//	{
//		printf("%s ", reserved[expr->operator]);
//		print_expr_prefix(expr->leftOperand);
//		print_expr_prefix(expr->rightOperand);
//	}
//
//}
void print_expr_prefix(struct exprNode* expr)
{
	if(expr->tag == EXPR)
	{
		if(expr->operator == DIV)
			printf("/ ");
		else if(expr->operator ==PLUS)
			printf("+ "); 
		else if (expr->operator ==MINUS)
			printf("- "); 
		else if(expr->operator == MULT)
			printf("* ");
		print_expr_prefix(expr->leftOperand);
		print_expr_prefix(expr->rightOperand);
	}
	else if(expr->tag == PRIMARY)
	{
		if(expr->leftOperand != NULL)
			print_expr_prefix(expr->leftOperand);
		else if(expr->primary != NULL)
			print_primary(expr->primary);
	}
}

void print_primary(struct primaryNode* prim)
{
	if(prim->tag == REALNUM)
	{
		printf("%.4f ", prim->fval); 
	}
	else if(prim->tag == ID)
	{
		printf("%s ", prim->id);
	}
	else if(prim->tag == NUM)
	{
		printf("%d ", prim->ival);
	}
}
void print_condition(struct conditionNode* condition)
{
	if(condition->relop == GREATER)
		printf("> ");
	else if(condition->relop == GTEQ)
		printf(">= ");
	else if(condition->relop ==LTEQ)
		printf("<= ");  
	else if(condition->relop == NOTEQUAL)
		printf("<> ");
	else if(condition->relop == LESS)
		printf("< ");
	print_primary(condition->left_operand);
	print_primary(condition->right_operand);
	printf("\n");
}


/*--------------------------------------------------------------------
CREATING PARSE TREE NODE
---------------------------------------------------------------------*/
struct programNode* make_programNode()
{	
	return (struct programNode*) malloc(sizeof(struct programNode));
}

struct conditionNode* make_conditionNode()
{
	return(struct conditionNode*) malloc(sizeof(struct conditionNode));
}

struct declNode* make_declNode()
{
	return (struct declNode*) malloc(sizeof(struct declNode));
}

struct type_decl_sectionNode* make_type_decl_sectionNode()
{
	return (struct type_decl_sectionNode*) malloc(sizeof(struct type_decl_sectionNode));
}

struct var_decl_sectionNode* make_var_decl_sectionNode()
{
	return (struct var_decl_sectionNode*) malloc(sizeof(struct var_decl_sectionNode));
}

struct var_declNode* make_var_declNode()
{
	return (struct var_declNode*) malloc(sizeof(struct var_declNode));
}

struct type_declNode* make_type_declNode()
{
	return (struct type_declNode*) malloc(sizeof(struct type_declNode));
}

struct type_decl_listNode* make_type_decl_listNode()
{
	return (struct type_decl_listNode*) malloc(sizeof(struct type_decl_listNode));
}

struct var_decl_listNode* make_var_decl_listNode()
{
	return (struct var_decl_listNode*) malloc(sizeof(struct var_decl_listNode));
}

struct id_listNode* make_id_listNode()
{
	return (struct id_listNode*) malloc(sizeof(struct id_listNode));
}

struct type_nameNode* make_type_nameNode()
{
	return (struct type_nameNode*) malloc(sizeof(struct type_nameNode));
}

struct bodyNode* make_bodyNode()
{
	return (struct bodyNode*) malloc(sizeof(struct bodyNode));
}

struct stmt_listNode* make_stmt_listNode()
{
	return (struct stmt_listNode*) malloc(sizeof(struct stmt_listNode));
}

struct stmtNode* make_stmtNode()
{
	return (struct stmtNode*) malloc(sizeof(struct stmtNode));
}

struct while_stmtNode* make_while_stmtNode()
{
	return (struct while_stmtNode*) malloc(sizeof(struct while_stmtNode));
}

struct assign_stmtNode* make_assign_stmtNode()
{
	return (struct assign_stmtNode*) malloc(sizeof(struct assign_stmtNode));
}

struct exprNode* make_exprNode()
{
	return (struct exprNode*) malloc(sizeof(struct exprNode));
}

struct primaryNode* make_primaryNode()
{
	return (struct primaryNode*) malloc(sizeof(struct primaryNode));
}

/*--------------------------------------------------------------------*/

/*--------------------------------------------------------------------
PARSING AND BUILDING PARSE TREE
---------------------------------------------------------------------*/
struct primaryNode* primary()
{
	struct primaryNode* tName;
	tName = make_primaryNode();

	ttype = getToken();

	if(ttype == ID)
	{
		tName->tag = ID;
		tName->id = (char *) malloc(tokenLength+1);
		strcpy(tName->id,token);
		return tName;

	}
	else if(ttype == NUM)
	{
		tName->tag = NUM;
		tName->ival = atoi(token);
		return tName;
	}
	else if(ttype == REALNUM)
	{
		tName->tag = REALNUM;
		tName->fval = atof(token);
		return tName;
	}
	else
	{
		syntax_error("primary. NUM, REALNUM, or ID expected", line_no);
		exit(0);
	}

}

struct conditionNode* condition()
{

	struct conditionNode* tName;
	tName = make_conditionNode();
	ttype= getToken();
	if(ttype > 32 || ttype < 36)
	{
		ungetToken();
		tName->left_operand = primary();
		ttype = getToken();
		if(ttype > 31|| ttype < 27)
		{
			tName->relop = ttype;
			ttype = getToken();
			if(ttype > 32 || ttype < 36)
			{
				ungetToken();
				tName->right_operand = primary();
				return tName;
			}
			else 
			{
				syntax_error("condition. NUM REALNUM or ID expected", line_no);
				exit(0);
			}
		}
		else 
		{
			syntax_error("condition. GREATER GTEQ LESS NOTEQUAL or LTEQ expected", line_no);
			exit(0);
		}

	}
	else 
	{
		syntax_error("condition. NUM REALNUM or ID expected", line_no);
		exit(0);
	}
}

struct exprNode* factor()
{
	struct exprNode* tName;
	tName = make_exprNode();



	//tName->tag = expr();

	ttype = getToken();

	if(ttype == LPAREN)
	{
		if(ttype == LPAREN || ttype == NUM || ttype == REALNUM || ttype == ID)
		{
			ungetToken();
			tName->leftOperand = expr();
			tName->primary = NULL;
			tName->rightOperand=NULL;
			tName->tag = PRIMARY;
			tName->operator = NOOP;
			ttype = getToken();


			if(ttype == RPAREN)
			{
				return tName;
			}
			else
			{
				syntax_error("factor. RPAREN expected", line_no);
				exit(0);
			}
		}
		else
		{
			syntax_error("factor. LPAREN NUM REALNUM or ID expected", line_no);
			exit(0);
		}
	}
	else
	{
		ungetToken();
		tName->leftOperand = NULL;
		tName->primary = primary();
		tName->rightOperand=NULL;
		tName->tag = PRIMARY;
		tName->operator = NOOP;
		return tName;
	}
}

struct exprNode* term()
{
	struct exprNode* tName;
	tName = make_exprNode();

	ttype = getToken();
	if(ttype == LPAREN || ttype > 32 || ttype < 36)
	{
		ungetToken();
		tName->leftOperand  = factor();

		ttype = getToken();

		if(ttype == MULT || ttype == DIV)
		{
			tName->operator = ttype;
			tName->tag = EXPR;
			ttype = getToken();
			if(ttype == LPAREN || ttype > 32 || ttype < 36)
			{
				ungetToken();
				tName->rightOperand = term();
				return tName;
			}
			else
			{
				syntax_error("term. LPAREN NUM REALNUM or ID expected", line_no);
				exit(0);		
			}
		}
		else 
		{
			ungetToken();
			tName->primary = NULL;
			tName->rightOperand=NULL;
			tName->tag = PRIMARY;
			tName->operator = NOOP;
			return tName;

		}
	}
	else
	{
		syntax_error("term. LPAREN NUM REALNUM or ID expected", line_no);
		exit(0);	

	}

}


struct exprNode* expr()
{
	struct exprNode* tName;
	tName = make_exprNode();

	ttype = getToken();
	if(ttype == LPAREN || ttype > 32 || ttype < 36)
	{
		ungetToken();
		tName->leftOperand  = term();

		ttype = getToken();

		if(ttype == PLUS || ttype == MINUS)
		{
			tName->operator = ttype;
			tName->tag = EXPR;
			ttype = getToken();
			if(ttype == LPAREN || ttype > 32 || ttype < 36)
			{
				ungetToken();
				tName->rightOperand = expr();
				return tName;
			}
			else
			{
				syntax_error("expr. LPAREN NUM REALNUM or ID expected", line_no);
				exit(0);		
			}
		}
		else 
		{
			ungetToken();
			tName->primary = NULL;
			tName->rightOperand=NULL;
			tName->tag = PRIMARY;
			tName->operator = NOOP;
			return tName;

		}
	}
	else
	{
		syntax_error("expr. LPAREN NUM REALNUM or ID expected", line_no);
		exit(0);	

	}

}

struct assign_stmtNode* assign_stmt()
{	
	struct assign_stmtNode* tName;
	tName = make_assign_stmtNode();

	ttype = getToken();

	if(ttype == ID)
	{
		tName->id = (char *) malloc(tokenLength+1);
		strcpy(tName->id,token);

		ttype = getToken();

		if(ttype == EQUAL)
		{
			ttype = getToken();
			if(ttype == LPAREN || ttype > 32 || ttype < 36)
			{
				ungetToken();
				tName->expr = expr();
				ttype = getToken();


				if(ttype==SEMICOLON)
				{
					return tName;
				}
				else
				{
					syntax_error("assign_stmt. SEMICOLON expected", line_no);
					exit(0);
				}

			}
			else
			{
				syntax_error("expr. LPAREN NUM REALNUM or ID expected", line_no);
				exit(0);	
			}
		}
		else
		{
			syntax_error("assign_stmt. EQUAL expected", line_no);
			exit(0);
		}
	}
	else
	{
		syntax_error("assign_stmt. ID expected", line_no);
		exit(0);
	}


}

struct while_stmtNode* while_stmt()
{
	struct while_stmtNode* tName;
	tName = make_while_stmtNode();
	ttype = getToken();
	if(ttype == WHILE)
	{
		ttype = getToken();
		if( ttype > 32 || ttype < 36)
		{
			ungetToken();
			tName->condition = condition();
			ttype = getToken();
			if(ttype = LBRACE)
			{
				ungetToken();
				tName->body = body();
				return tName;
			}
			else
			{
				syntax_error("while_stmt. LBRACE expected", line_no);
				exit(0);			

			}

		}
		else
		{
			syntax_error("while_stmt. NUM REALNUM or ID expected", line_no);
			exit(0);	
		}
	}
	else 
	{
		syntax_error("while. NUM REALNUM or ID expected", line_no);
		exit(0);
	}

}

struct stmtNode* stmt()
{
	struct stmtNode* tName;
	tName = make_stmtNode();

	ttype = getToken();
	if(ttype == WHILE)
	{	
		ungetToken();
		tName->while_stmt = while_stmt();
		tName->assign_stmt = NULL;
		tName->stmtType = WHILE;
		return tName;
	}
	else if(ttype == ID)
	{
		ungetToken();
		tName->while_stmt = NULL;
		tName->assign_stmt = assign_stmt();
		tName->stmtType = ASSIGN;
		return tName;
	}
	else
	{
		syntax_error("stmt. WHILE or ID expected", line_no);
		exit(0);
	}
}

struct stmt_listNode* stmt_list()
{
	struct stmt_listNode* tName;
	tName = make_stmt_listNode();

	ttype = getToken();
	if(ttype == WHILE || ttype == ID)
	{
		ungetToken();
		tName->stmt = stmt();
		ttype = getToken();
		if(ttype == WHILE || ttype == ID)
		{
			ungetToken();
			tName->stmt_list = stmt_list();

		}
		else
		{
			ungetToken();
			tName->stmt_list = NULL;
		}
		return tName;
	}
	else
	{
		syntax_error("stmt_list. WHILE or ID expected", line_no);
		exit(0);
	}


}

struct bodyNode* body()
{	
	struct bodyNode* tName;
	tName = make_bodyNode();

	ttype = getToken();
	if(ttype == LBRACE)
	{
		ttype = getToken();
		if(ttype == WHILE || ttype == ID)
		{
			ungetToken();
			tName->stmt_list = stmt_list();
			ttype = getToken();
			if(ttype == RBRACE)
			{
				return tName;
			}
			else
			{
				syntax_error("body. RBRACE expected", line_no);
				exit(0);
			}
		}
		else
		{
				syntax_error("body. WHILE or ID expected", line_no);
				exit(0);
		}

	}
	else
	{	syntax_error("body. LBRACE expected", line_no);
	exit(0);
	}

}

struct type_nameNode* type_name()
{
	struct type_nameNode* tName;
	tName = make_type_nameNode();

	ttype = getToken();
	if ((ttype == ID)|(ttype == INT)|(ttype==REAL)
		|(ttype == STRING)|(ttype==BOOLEAN))
	{	tName->type = ttype;
	if (ttype == ID)
	{	tName->id = (char *) malloc(tokenLength+1);
	strcpy(tName->id,token);	
	}
	return tName;
	} else
	{	syntax_error("type_name. type name expected", line_no);
	exit(0);
	}
}

struct id_listNode* id_list()
{
	struct id_listNode* idList;
	idList = make_id_listNode();
	ttype = getToken();
	if (ttype == ID)
	{	
		idList->id = (char*) malloc(tokenLength+1);
		strcpy(idList->id, token);
		ttype = getToken();
		if (ttype == COMMA)
		{
			idList->id_list = id_list();
			return idList;

		}
		else if (ttype == COLON)
		{	
			ungetToken();
			idList->id_list = NULL;
			return idList;
		} 
		else
		{
			syntax_error("id_list. COMMA or COLON expected", line_no);
			exit(0);
		}
	}
	else
	{
		syntax_error("id_list. ID expected", line_no);
		exit(0);
	}

}

struct type_declNode* type_decl()
{	
	struct type_declNode* typeDecl;
	typeDecl = make_type_declNode();
	ttype = getToken();
		if (ttype == ID)
		{	ungetToken();
			typeDecl->id_list = id_list();
			ttype = getToken();
			if (ttype == COLON)
			{	typeDecl->type_name = type_name();
				ttype = getToken();
			if (ttype == SEMICOLON)
			{	
				return typeDecl;
			}
			else
			{	syntax_error("type_decl. SEMICOLON expected", line_no);
				exit(0);
			}
		} 
	}
}

struct var_declNode* var_decl()
{
	struct var_declNode* varDecl;
	varDecl = make_var_declNode();
	ttype = getToken();
	if (ttype == ID)
	{	
		ungetToken();
		varDecl->id_list = id_list();
		ttype = getToken();
		if (ttype == COLON)
		{	
			varDecl->type_name = type_name();
			ttype = getToken();
			if (ttype == SEMICOLON)
			{	
				return varDecl;
			}
			else
			{	
				syntax_error("var_decl. SEMICOLON expected", line_no);
				exit(0);
			}
		} 
	}
}	

struct var_decl_listNode* var_decl_list()
{
	struct var_decl_listNode* varDeclList;
	varDeclList = make_var_decl_listNode();

	ttype = getToken();
	if (ttype == ID)
	{	
		ungetToken();
		varDeclList->var_decl = var_decl();
		ttype = getToken();
		if (ttype == ID)
		{	
			ungetToken();
			varDeclList->var_decl_list = var_decl_list();
			return varDeclList;
		}  
		else	
		{
			ungetToken();
			varDeclList->var_decl_list = NULL;
			return varDeclList;
		} 
	} 
	else
	{
		syntax_error("var_decl_list. ID expected", line_no);
		exit(0);
	} 
}

struct type_decl_listNode* type_decl_list()
{
	struct type_decl_listNode* typeDeclList;
	typeDeclList = make_type_decl_listNode();

	ttype = getToken();
	if (ttype == ID)
	{	ungetToken();
	typeDeclList->type_decl = type_decl();
	ttype = getToken();
	if (ttype == ID)
	{	ungetToken();
	typeDeclList->type_decl_list = type_decl_list();
	return typeDeclList;
	}  else	
	{	ungetToken();
	return typeDeclList;
	} 
	} else
	{	syntax_error("type_decl_list. ID expected", line_no);
	exit(0);
	} 
}

struct var_decl_sectionNode* var_decl_section()
{
	struct var_decl_sectionNode *varDeclSection;
	varDeclSection = make_var_decl_sectionNode();

	ttype = getToken();
	if (ttype == VAR)
	{	// no need to ungetToken() 
		varDeclSection->var_decl_list = var_decl_list();  
		return varDeclSection;
	} else
	{	syntax_error("var_decl_section. VAR expected", line_no);
	exit(0);
	}
}

struct type_decl_sectionNode* type_decl_section()
{
	struct type_decl_sectionNode *typeDeclSection;
	typeDeclSection = make_type_decl_sectionNode();

	ttype = getToken();
	if (ttype == TYPE)
	{
		typeDeclSection->type_decl_list = type_decl_list();
		return typeDeclSection;            
	} else
	{	syntax_error("type_decl_section. TYPE expected", line_no);
	exit(0);
	}
}


struct declNode* decl()
{	
	struct declNode* dec;
	dec = make_declNode();

	ttype = getToken();

	if (ttype == TYPE)
	{	ungetToken();
		dec->type_decl_section = type_decl_section();
		ttype = getToken();

		if (ttype == VAR)
		{	// type_decl_list is epsilon
			// or type_decl already parsed and the 
			// next token is checked
			ungetToken();
			dec->var_decl_section = var_decl_section();
		} 
		else
		{	
			ungetToken();
			dec->var_decl_section = NULL;
		}
		return dec;
	
	} 
	else
	{
		dec->type_decl_section = NULL; 
		if (ttype == VAR)
		{	// type_decl_list is epsilon
			// or type_decl already parsed and the 
			// next token is checked
			ungetToken(); 
			dec->var_decl_section = var_decl_section();
			return dec;
		}
		
		else
		{	
			if (ttype == LBRACE)
			{	
				ungetToken();	
				dec->var_decl_section = NULL;
				return dec;
			} 
			else
			{	
				syntax_error("decl. LBRACE expected", line_no);
				exit(0);		// stop after first syntax error
			}
		}
	}
}

struct programNode* program()
{	
	struct programNode* prog;
	prog = make_programNode();
	ttype = getToken();

	if ((ttype == TYPE) | (ttype == VAR) | (ttype == LBRACE))
	{	
		ungetToken();  
		prog->decl = decl();
		prog->body = body(); 
		// I should really be checking for FIRST(body) before calling body()
		// but it is not an issue because there is no other
		// option. So I leave the complaining to body().
		//getToken();
		//	if(ttype != EOF)
		//	{
		//		syntax_error("program. EOF expected", line_no);
		//		exit(0);
		//	}
		return prog;
	} 
	else
	{	
		syntax_error("program. TYPE or VAR or LBRACE expected", line_no);
		exit(0);		// stop after first syntax error
	}
}

// COMMON mistakes:
//    *     = instead of ==
//    *     not allocating space before strcpy
main()
{       
	struct programNode* parseTree;
	parseTree = program();
	print_parse_tree(parseTree);
	printf("\nSUCCESSFULLY PARSED INPUT!\n");
}

